package com.evan.review.basic.collection;

import android.os.Bundle;
import android.widget.TextView;
import androidx.appcompat.app.AppCompatActivity;
import com.evan.review.R;
import java.util.HashSet;
import java.util.Set;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.TreeSet;

/**
 * HashSet详解Activity
 * 
 * 本Activity详细介绍HashSet的实现原理、特性和使用方法：
 * 1. HashSet的底层数据结构与实现
 * 2. HashSet常用操作与性能分析
 * 3. HashSet、LinkedHashSet与TreeSet的对比
 * 4. HashSet正确使用方式与陷阱
 * 5. HashSet相关面试题
 */
public class HashSetActivity extends AppCompatActivity {
    
    private TextView tvOutput;
    
    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_data_structure);
        
        setTitle("HashSet详解");
        
        tvOutput = findViewById(R.id.tv_output);
        
        // 展示HashSet基本原理
        demonstrateHashSetPrinciple();
        
        // 展示HashSet基本操作
        demonstrateHashSetOperations();
        
        // 展示HashSet家族对比
        demonstrateSetComparison();
        
        // 展示HashSet使用注意事项
        demonstrateHashSetPitfalls();
        
        // 展示HashSet相关面试题
        demonstrateInterviewQuestions();
    }
    
    /**
     * 展示HashSet的基本原理
     */
    private void demonstrateHashSetPrinciple() {
        StringBuilder output = new StringBuilder();
        output.append("=== HashSet底层原理 ===\n\n");
        
        // 1. 底层实现
        output.append("1. 底层实现：\n");
        output.append("• HashSet内部使用HashMap实现\n");
        output.append("• HashSet的元素存储为HashMap的key\n");
        output.append("• HashMap的value使用一个名为PRESENT的静态Object对象\n");
        output.append("• 源码实现核心：\n");
        output.append("  private transient HashMap<E,Object> map;\n");
        output.append("  private static final Object PRESENT = new Object();\n");
        output.append("  public boolean add(E e) {\n");
        output.append("      return map.put(e, PRESENT) == null;\n");
        output.append("  }\n\n");
        
        // 2. 核心特性
        output.append("2. 核心特性：\n");
        output.append("• 不允许重复元素（基于HashMap key的唯一性）\n");
        output.append("• 允许null元素（只能有一个）\n");
        output.append("• 无序集合，不保证元素顺序\n");
        output.append("• 非线程安全\n");
        output.append("• 不保证元素的存储顺序不变\n\n");
        
        // 3. 性能特点
        output.append("3. 性能特点：\n");
        output.append("• 添加、删除、判断元素是否存在的时间复杂度为O(1)\n");
        output.append("• 依赖元素的hashCode()和equals()方法\n");
        output.append("• 初始容量默认为16，负载因子为0.75\n");
        output.append("• 扩容策略与HashMap相同\n");
        
        updateOutput(output.toString());
    }
    
    /**
     * 展示HashSet基本操作
     */
    private void demonstrateHashSetOperations() {
        StringBuilder output = new StringBuilder();
        output.append("\n=== HashSet基本操作 ===\n\n");
        
        // 创建HashSet
        Set<String> set = new HashSet<>();
        
        // 1. 添加元素
        output.append("1. 添加元素：\n");
        output.append("Set<String> set = new HashSet<>();\n");
        output.append("set.add(\"Java\");       // 添加元素, O(1)\n");
        set.add("Java");
        output.append("set.add(\"Python\");     // 添加元素, O(1)\n");
        set.add("Python");
        output.append("set.add(\"Java\");       // 重复元素不会被添加, 返回false\n");
        boolean added = set.add("Java");
        output.append("// 添加重复元素返回: " + added + "\n");
        output.append("// 当前set: " + set + "\n\n");
        
        // 2. 删除元素
        output.append("2. 删除元素：\n");
        output.append("set.remove(\"Java\");    // 删除元素, O(1)\n");
        set.remove("Java");
        output.append("// 当前set: " + set + "\n");
        output.append("set.remove(\"C++\");     // 删除不存在的元素, 返回false\n");
        boolean removed = set.remove("C++");
        output.append("// 删除不存在元素返回: " + removed + "\n\n");
        
        // 3. 判断元素是否存在
        set.add("Kotlin");
        output.append("3. 判断元素是否存在：\n");
        output.append("set.contains(\"Kotlin\"); // 检查元素是否存在, O(1)\n");
        output.append("// 返回: " + set.contains("Kotlin") + "\n");
        output.append("set.contains(\"Java\");   // 检查元素是否存在, O(1)\n");
        output.append("// 返回: " + set.contains("Java") + "\n\n");
        
        // 4. 集合操作
        output.append("4. 集合操作：\n");
        output.append("// 创建两个集合\n");
        output.append("Set<String> set1 = new HashSet<>();\n");
        output.append("set1.add(\"A\"); set1.add(\"B\"); set1.add(\"C\");\n");
        Set<String> set1 = new HashSet<>();
        set1.add("A"); set1.add("B"); set1.add("C");
        
        output.append("Set<String> set2 = new HashSet<>();\n");
        output.append("set2.add(\"B\"); set2.add(\"C\"); set2.add(\"D\");\n");
        Set<String> set2 = new HashSet<>();
        set2.add("B"); set2.add("C"); set2.add("D");
        
        output.append("\n// 并集（修改set1）\n");
        output.append("set1.addAll(set2);\n");
        Set<String> unionSet = new HashSet<>(set1);
        unionSet.addAll(set2);
        output.append("// 并集结果: " + unionSet + "\n");
        
        set1 = new HashSet<>();
        set1.add("A"); set1.add("B"); set1.add("C");
        
        output.append("\n// 交集（修改set1）\n");
        output.append("set1.retainAll(set2);\n");
        Set<String> intersectionSet = new HashSet<>(set1);
        intersectionSet.retainAll(set2);
        output.append("// 交集结果: " + intersectionSet + "\n");
        
        set1 = new HashSet<>();
        set1.add("A"); set1.add("B"); set1.add("C");
        
        output.append("\n// 差集（修改set1）\n");
        output.append("set1.removeAll(set2);\n");
        Set<String> differenceSet = new HashSet<>(set1);
        differenceSet.removeAll(set2);
        output.append("// 差集结果: " + differenceSet + "\n\n");
        
        // 5. 遍历方式
        output.append("5. 遍历方式：\n");
        Set<String> languages = new HashSet<>();
        languages.add("Java");
        languages.add("Python");
        languages.add("Kotlin");
        
        output.append("// 方式1: 增强for循环\n");
        output.append("for (String lang : languages) {\n");
        output.append("    System.out.println(lang);\n");
        output.append("}\n\n");
        
        output.append("// 方式2: 迭代器\n");
        output.append("Iterator<String> iterator = languages.iterator();\n");
        output.append("while (iterator.hasNext()) {\n");
        output.append("    System.out.println(iterator.next());\n");
        output.append("}\n\n");
        
        output.append("// 方式3: Lambda表达式 (Java 8+)\n");
        output.append("languages.forEach(lang -> System.out.println(lang));\n");
        
        updateOutput(output.toString());
    }
    
    /**
     * 展示HashSet家族对比
     */
    private void demonstrateSetComparison() {
        StringBuilder output = new StringBuilder();
        output.append("\n=== Set家族对比 ===\n\n");
        
        // 1. 创建不同Set实现
        output.append("1. 三种Set实现类比较：\n");
        output.append("// 添加相同的元素到不同Set\n");
        output.append("Set<String> hashSet = new HashSet<>();\n");
        output.append("Set<String> linkedHashSet = new LinkedHashSet<>();\n");
        output.append("Set<String> treeSet = new TreeSet<>();\n\n");
        
        Set<String> hashSet = new HashSet<>();
        Set<String> linkedHashSet = new LinkedHashSet<>();
        Set<String> treeSet = new TreeSet<>();
        
        String[] data = {"C", "A", "B", "E", "D"};
        for (String item : data) {
            hashSet.add(item);
            linkedHashSet.add(item);
            treeSet.add(item);
        }
        
        output.append("// 添加顺序: C, A, B, E, D\n");
        output.append("HashSet: " + hashSet + " (无序)\n");
        output.append("LinkedHashSet: " + linkedHashSet + " (保持插入顺序)\n");
        output.append("TreeSet: " + treeSet + " (自然排序)\n\n");
        
        // 2. 性能和特性对比
        output.append("2. 性能和特性对比：\n");
        output.append("┌──────────────┬────────────┬───────────────┬────────────┐\n");
        output.append("│ 特性         │ HashSet    │ LinkedHashSet │ TreeSet    │\n");
        output.append("├──────────────┼────────────┼───────────────┼────────────┤\n");
        output.append("│ 底层实现     │ HashMap    │ LinkedHashMap │ TreeMap    │\n");
        output.append("│ 有序性       │ 无序       │ 插入顺序      │ 自然顺序   │\n");
        output.append("│ add/contains │ O(1)       │ O(1)          │ O(log n)   │\n");
        output.append("│ 迭代性能     │ O(h/n)     │ O(n)          │ O(n)       │\n");
        output.append("│ 内存消耗     │ 低         │ 中等          │ 高         │\n");
        output.append("└──────────────┴────────────┴───────────────┴────────────┘\n\n");
        
        // 3. 适用场景
        output.append("3. 适用场景：\n");
        output.append("• HashSet适合：\n");
        output.append("  - 不关心元素顺序，追求最高性能\n");
        output.append("  - 需要快速判断元素是否存在\n");
        output.append("  - 内存敏感的应用\n\n");
        
        output.append("• LinkedHashSet适合：\n");
        output.append("  - 需要保持插入顺序\n");
        output.append("  - 需要按照插入顺序迭代元素\n");
        output.append("  - 实现LRU缓存等需要有序且唯一的结构\n\n");
        
        output.append("• TreeSet适合：\n");
        output.append("  - 需要元素始终保持排序状态\n");
        output.append("  - 需要获取有序区间的元素\n");
        output.append("  - 需要获取最大/最小元素\n");
        
        updateOutput(output.toString());
    }
    
    /**
     * 展示HashSet使用注意事项
     */
    private void demonstrateHashSetPitfalls() {
        StringBuilder output = new StringBuilder();
        output.append("\n=== HashSet使用注意事项 ===\n\n");
        
        // 1. hashCode和equals的重要性
        output.append("1. hashCode和equals的重要性：\n");
        output.append("• HashSet判断元素是否重复依赖于hashCode()和equals()方法\n");
        output.append("• 自定义对象必须正确覆写这两个方法\n");
        output.append("• 正确实现原则：\n");
        output.append("  1. 相等的对象必须有相同的hashCode\n");
        output.append("  2. 相同hashCode的对象不一定相等，需要通过equals进一步判断\n");
        output.append("  3. equals方法一致性：x.equals(y) 与 y.equals(x) 结果相同\n");
        output.append("  4. 修改equals时必须同时修改hashCode\n\n");
        
        // 2. 错误的hashCode/equals实现
        output.append("2. 错误的hashCode/equals实现：\n");
        output.append("// 错误的实现 - 只覆写equals不覆写hashCode\n");
        output.append("class Person {\n");
        output.append("    private String name;\n");
        output.append("    private int age;\n\n");
        
        output.append("    // 只覆写equals\n");
        output.append("    @Override\n");
        output.append("    public boolean equals(Object obj) {\n");
        output.append("        if (this == obj) return true;\n");
        output.append("        if (!(obj instanceof Person)) return false;\n");
        output.append("        Person other = (Person) obj;\n");
        output.append("        return name.equals(other.name) && age == other.age;\n");
        output.append("    }\n");
        output.append("    // 没有覆写hashCode - 将导致相等对象可能有不同hashCode\n");
        output.append("}\n\n");
        
        // 3. 正确的hashCode/equals实现
        output.append("3. 正确的hashCode/equals实现：\n");
        output.append("// 正确的实现 - 同时覆写equals和hashCode\n");
        output.append("class Person {\n");
        output.append("    private String name;\n");
        output.append("    private int age;\n\n");
        
        output.append("    @Override\n");
        output.append("    public boolean equals(Object obj) {\n");
        output.append("        if (this == obj) return true;\n");
        output.append("        if (!(obj instanceof Person)) return false;\n");
        output.append("        Person other = (Person) obj;\n");
        output.append("        return name.equals(other.name) && age == other.age;\n");
        output.append("    }\n\n");
        
        output.append("    @Override\n");
        output.append("    public int hashCode() {\n");
        output.append("        int result = name != null ? name.hashCode() : 0;\n");
        output.append("        result = 31 * result + age;\n");
        output.append("        return result;\n");
        output.append("    }\n");
        output.append("}\n\n");
        
        // 4. 可变对象的风险
        output.append("4. 可变对象的风险：\n");
        output.append("• 添加到HashSet的对象不应在添加后修改影响hashCode的字段\n");
        output.append("• 原因：修改后对象的hashCode变化，导致HashSet无法正确查找元素\n");
        output.append("• 错误示例：\n");
        output.append("  Set<Person> set = new HashSet<>();\n");
        output.append("  Person p = new Person(\"Tom\", 20);\n");
        output.append("  set.add(p);             // 添加对象\n");
        output.append("  p.setName(\"Jerry\");    // 修改对象名称\n");
        output.append("  System.out.println(set.contains(p)); // 返回false\n");
        
        updateOutput(output.toString());
    }
    
    /**
     * 展示HashSet相关面试题
     */
    private void demonstrateInterviewQuestions() {
        StringBuilder output = new StringBuilder();
        output.append("\n=== HashSet面试题 ===\n\n");
        
        // 1. HashSet与HashMap的关系
        output.append("1. HashSet与HashMap的关系是什么？\n");
        output.append("答：HashSet内部使用HashMap实现：\n");
        output.append("• HashSet将元素存储为HashMap的键\n");
        output.append("• 所有HashMap键对应的值都是同一个Object常量(PRESENT)\n");
        output.append("• HashSet的实现原理很简单，基本将操作都委托给内部的HashMap\n");
        output.append("• 因此HashSet继承了HashMap的性能特点和限制\n\n");
        
        // 2. 三种Set实现的区别
        output.append("2. HashSet、LinkedHashSet和TreeSet有什么区别？\n");
        output.append("答：主要区别在于实现、性能和有序性：\n");
        output.append("• HashSet：基于HashMap实现，无序，性能最佳\n");
        output.append("• LinkedHashSet：基于LinkedHashMap实现，保持插入顺序，性能次之\n");
        output.append("• TreeSet：基于TreeMap(红黑树)实现，自然排序或自定义比较器排序，性能较差\n");
        output.append("• 它们的共同点是都不允许重复元素\n\n");
        
        // 3. HashSet去重原理
        output.append("3. HashSet如何保证元素不重复？\n");
        output.append("答：HashSet通过HashMap的键唯一性保证元素不重复：\n");
        output.append("• 添加元素时，HashSet将元素作为HashMap的键存储\n");
        output.append("• 判断元素是否重复的步骤：\n");
        output.append("  1. 计算元素的hashCode值确定存储桶\n");
        output.append("  2. 若桶中有元素，则使用equals方法逐个比较\n");
        output.append("  3. 若找到equals返回true的元素，则视为重复，添加失败\n");
        output.append("  4. 否则，视为新元素，添加成功\n\n");
        
        // 4. HashSet与ArrayList的选择
        output.append("4. 什么时候应该使用HashSet而不是ArrayList？\n");
        output.append("答：选择依据：\n");
        output.append("• 使用HashSet的场景：\n");
        output.append("  - 需要元素唯一性，不允许重复\n");
        output.append("  - 不关心元素的顺序\n");
        output.append("  - 需要高效判断元素是否存在(contains操作)\n");
        output.append("  - 需要去重\n");
        output.append("• 使用ArrayList的场景：\n");
        output.append("  - 允许元素重复\n");
        output.append("  - 需要保持元素插入顺序\n");
        output.append("  - 需要通过索引随机访问元素\n");
        output.append("  - 需要频繁遍历集合\n\n");
        
        // 5. 线程安全问题
        output.append("5. HashSet是线程安全的吗？如何实现线程安全？\n");
        output.append("答：HashSet不是线程安全的。线程安全解决方案：\n");
        output.append("• 使用Collections.synchronizedSet包装：\n");
        output.append("  Set<E> syncSet = Collections.synchronizedSet(new HashSet<>());\n");
        output.append("• 使用ConcurrentHashMap模拟：\n");
        output.append("  Set<E> concurrentSet = Collections.newSetFromMap(\n");
        output.append("      new ConcurrentHashMap<E, Boolean>());\n");
        output.append("• 使用CopyOnWriteArraySet：\n");
        output.append("  Set<E> cowSet = new CopyOnWriteArraySet<>(); // 适合读多写少场景\n");
        output.append("• 使用显式锁或同步块：\n");
        output.append("  synchronized(set) { set.add(e); }\n");
        
        updateOutput(output.toString());
    }
    
    /**
     * 更新输出文本
     */
    private void updateOutput(String text) {
        tvOutput.append(text);
    }
} 